package com.c2b.algorithm.leetcode.base;

import java.util.LinkedList;
import java.util.Queue;

/**
 * <a href="https://leetcode.cn/problems/populating-next-right-pointers-in-each-node-ii/">填充每个节点的下一个右侧节点指针 II(Populating Next Right Pointers in Each Node II)</a>
 * <p>给定一个二叉树：
 * <pre>
 * struct Node {
 *   int val;
 *   Node *left;
 *   Node *right;
 *   Node *next;
 * }
 * </pre>
 * <p>
 * 填充它的每个 next 指针，让这个指针指向其下一个右侧节点。如果找不到下一个右侧节点，则将 next 指针设置为 NULL 。
 * 初始状态下，所有 next 指针都被设置为 NULL 。
 * </p>
 * <p>
 * <b>示例：</b>
 * <pre>
 * 示例 1：
 *      输入：root = [1,2,3,4,5,null,7]
 *                  1
 *                 / \
 *                2   3
 *               / \   \
 *              4   5   7
 *      输出：[1,#,2,3,#,4,5,7,#]
 *                  1->null
 *                 / \
 *                2-> 3->null
 *               / \   \
 *              4 ->5 ->7->null
 * 示例 2：
 *      输入：root = []
 *      输出：[]
 * </pre>
 * </p>
 * <p>
 * <b>提示：</b>
 *     <ul>
 *      <li>树中的节点数在范围 [0, 6000] 内</li>
 *      <li>-100 <= Node.val <= 100</li>
 *     </ul>
 * </p>
 * <b>进阶：</b>
 * <li>你只能使用常量级额外空间。</li>
 * <li>使用递归解题也符合要求，本题中递归程序的隐式栈空间不计入额外空间复杂度。</li>
 *
 * @author c2b
 * @since 2023/4/28 13:46
 */
public class LC0117PopulatingNextRightPointersInEachNode_II_M {

    static class Solution {

        /**
         * 方法一：逻辑较清晰，代码简单。遍历当前层的时候，创建一个哑节点用于将下一层的所有节点串起来。
         */
        public Node connect(Node root) {
            if (root == null) {
                return null;
            }
            Node currNode = root;
            while (currNode != null) {
                // 创建一个哑节点。通过遍历当前层，把下一层的节点串起来
                Node dummyNode = new Node(-1);
                Node tempNode = dummyNode;
                while (currNode != null) {
                    if (currNode.left != null) {
                        tempNode.next = currNode.left;
                        tempNode = tempNode.next;
                    }
                    if (currNode.right != null) {
                        tempNode.next = currNode.right;
                        tempNode = tempNode.next;
                    }
                    // 继续访问这一行的下一个节点
                    currNode = currNode.next;
                }
                // 进入下一层
                currNode = dummyNode.next;
            }
            return root;
        }

        /**
         * 方法二：逻辑清晰，代码稍复杂。使用一个变量去记录下一层的最左节点
         */
        public Node connect2(Node root) {
            if (root == null) {
                return null;
            }
            // currLevelLeftmostNode 用于记录每一层的最左边的节点，初始值为根节点。
            Node currLevelLeftmostNode = root;
            // 外层循环：遍历树的每一层，直到最底层。结束条件：当下一层没有子节点
            while (currLevelLeftmostNode != null) {
                Node currNode = currLevelLeftmostNode;
                // currLevelLeftmostNode 用于记录当前层的下一层最左边的节点。
                Node nextLevelLeftmostNode = null;
                while (currNode != null) {
                    // 如果 currNode 有左子节点，改变当前节点左子节点的`next`指针
                    if (currNode.left != null) {
                        if (currNode.right != null) {
                            currNode.left.next = currNode.right;
                        } else {
                            currNode.left.next = getNextNode(currNode);
                        }
                        // 是从左往右的第一个节点？更新 nextLevelLeftmostNode
                        if (nextLevelLeftmostNode == null) {
                            nextLevelLeftmostNode = currNode.left;
                        }
                    }
                    // 如果 currNode 有右子节点，改变当前节点右子节点的`next`指针
                    if (currNode.right != null) {
                        currNode.right.next = getNextNode(currNode);

                        // 是从左往右的第一个节点？更新 currLevelLeftmostNode
                        if (nextLevelLeftmostNode == null) {
                            nextLevelLeftmostNode = currNode.right;
                        }
                    }
                    currNode = currNode.next;
                }
                // 进入下一层
                currLevelLeftmostNode = nextLevelLeftmostNode;
            }
            return root;
        }

        /**
         * 对于currNode.right.next指针指向： 应该遍历当前层currNode右侧的每一个节点，找到第一个左子节点或者右子节点不为null的
         */
        private Node getNextNode(Node currNode) {
            while (currNode.next != null) {
                if (currNode.next.left != null) {
                    return currNode.next.left;
                }
                if (currNode.next.right != null) {
                    return currNode.next.right;
                }
                currNode = currNode.next;
            }
            return null;
        }

        /**
         * 方法三：使用了队列。空间复杂度较高
         */
        public Node connect3(Node root) {
            if (root == null) {
                return null;
            }
            Queue<Node> queue = new LinkedList<>();
            queue.offer(root);
            while (!queue.isEmpty()) {
                int size = queue.size();
                for (int i = 0; i < size; i++) {
                    Node node = queue.poll();
                    if (node.left != null) {
                        queue.offer(node.left);
                    }
                    if (node.right != null) {
                        queue.offer(node.right);
                    }
                    if (i != size - 1) {
                        node.next = queue.peek();
                    }
                }
            }
            return root;
        }
    }

    // Definition for a Node.
    static class Node {
        public int val;
        public Node left;
        public Node right;
        public Node next;

        public Node() {
        }

        public Node(int _val) {
            val = _val;
        }

        public Node(int _val, Node _left, Node _right, Node _next) {
            val = _val;
            left = _left;
            right = _right;
            next = _next;
        }
    }


    public static void main(String[] args) {
        Node node = new Node(1);
        node.left = new Node(2);
        node.right = new Node(3);
        node.left.left = new Node(4);
        node.left.right = new Node(5);
        node.right.right = new Node(7);
        //node.right.right = new Node(6);
        //node.left.left.left = new Node(7);
        //node.right.right.right = new Node(8);
        //Node node = new Node(1);
        //node.right = new Node(-9);
        //node.right.right = new Node(8);
        //node.right.right.left = new Node(4);
        //node.right.right.right = new Node(-3);
        //node.right.right.right.left = new Node(-3);
        //node.right.right.right.left.left = new Node(-6);
        //node.right.right.right.left.left.right = new Node(-6);
        //node.right.right.right.left.left.right.left = new Node(-4);
        //node.right.right.right.left.left.right.right = new Node(-9);
        //node.right.right.right.left.left.right.right.left = new Node(6);
        Node connect = new Solution().connect(node);
    }
}
